#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include <stdlib.h>

// typedef int SLDataType;

// typedef struct SeqList
// {
//     SLDataType* a;
//     int size;
//     int capacity;
// }SeqList;

// void SeqListInit(SeqList* psl)
// {
//     assert(psl);
//     psl->a = nullptr;
//     psl->size = 0;
//     psl->capacity = 0;
// }

// void SqlListDestory(SeqList* psl)
// {
//     assert(psl);
//     free(psl->a);
//     psl->a = nullptr;
//     psl->size = psl->capacity = 0;
// }

// void SqlListPrint(SeqList* psl)
// {
//     assert(psl);
//     for(int i =  0; i < psl->size; i++)
//     {
//         printf("%d ", psl->a[i]);
//     }
//     printf("\n");
// }

// void SqlCheckCapacity(SeqList* psl)
// {
//     if(psl->size == psl->capacity)
//     {
//         int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
//         SLDataType* newA = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
//         if(newA == nullptr)
//         {
//             printf("realloc fail!\n");
//             exit(1);
//         }
//         psl->a = newA;
//         psl->capacity = newcapacity;
//     }
// }

// void SeqListPushFront(SeqList* psl, SLDataType x)
// {
//     // assert(psl);
//     // SqlCheckCapacity(psl);
//     // for(int i = psl->size; i >= 0; i--)
//     // {
//     //     psl->a[i] = psl->a[i-1];
//     // }
//     // psl->a[0] = x;
//     // psl->size++;
//     SeqListInsert(psl, 0, x);
// }


// void SeqListPushBack(SeqList* psl, SLDataType x)
// {
//     // assert(psl);
//     // SqlCheckCapacity(psl);
//     // psl->a[psl->size] = x;
//     // psl->size++;
//     SeqListInsert(psl, psl->size, x);
// }

// void SeqListInsert(SeqList* psl,int pos, SLDataType x)
// {
//     assert(psl);
//     assert(pos >= 0 && pos <= psl->size);
//     SqlCheckCapacity(psl);
//     for(int i = psl->size; i > pos; i--)
//     {
//         psl->a[i] = psl->a[i-1];
//     }
//     psl->a[pos] = x;
//     psl->size++;
// }

// void SeqListPopFront(SeqList* psl)
// {
//     // assert(psl);
//     // assert(psl->size > 0);
//     // for(int i = 0; i < psl->size-1; i++)
//     // {
//     //     psl->a[i] = psl->a[i+1];
//     // }
//     // psl->size--;
//     SeqListErase(psl, 0);
// }

// void SeqListPopBack(SeqList* psl)
// {
//     // assert(psl);
//     // assert(psl->size > 0);
//     // psl->size--;
//     SeqListErase(psl, psl->size);
// }


// void SeqListErase(SeqList* psl, int pos)
// {
//     assert(psl);
//     assert(psl->size > 0);
//     assert(pos >= 0 && pos < psl->size);

//     for(int i = pos; i < psl->size-1; i++)
//     {
//         psl->a[i] = psl->a[i+1];
//     }
//     psl->size--;
// }


// int SeqListFind(SeqList* psl, SLDataType x)
// {
//     assert(psl);
//     for(int i = 0; i < psl->size; i++)
//     {
//         if(psl->a[i] == x)
//             return i;
//     }
//     return -1;
// }

// void SeqListModify(SeqList* psl, int pos, SLDataType x)
// {
//     assert(psl);
//     assert(pos >= 0 && pos < psl->size);

//     psl->a[pos] = x;
// }

template<class T>
class SeqList
{
public:
    //使用构造函数和析构函数进行初始化和销毁
    SeqList()
        :_a(nullptr)
        ,_size(0)
        ,_capacity(0)
    {}

    ~SeqList()
    {
        delete(_a);
        _a = nullptr;
        _size = _capacity = 0;
    }

    void CheckCapacity(SeqList* psl)
    {
        if(psl->_size == psl->_capacity)
        {
            int newcapacity = psl->_capacity == 0 ? 4 : psl->_capacity * 2;
            T* newA = new [newcapacity];
            for(int i =0; i < psl->_size; i++)
            {
                newA[i] = psl->_a[i];
            }
            psl->_a = newA;
            delete newA;
            newA = nullptr;
            psl->_capacity = newcapacity;
        }
    }

    void SqlListPrint(SeqList* psl)
    {
        assert(psl);
        for(int i = 0; i < psl->_size; i++)
        {
            cout << psl->_a[i] << " ";
        }
        cout << "\n";
    }

    void SeqListInsert(SeqList* psl, int pos, T x)
    {
        assert(psl);
        assert(pos >= 0 && pos <= psl->_size);
        for(int i = psl->_size; i > pos; i--)
        {
            psl->_a[i] = psl->a[i-1];
        }
        psl->_a[pos] = x;
        psl->_size++;
    }

    void SeqListPushFront(SeqList* psl, T x)
    {
        SeqListInsert(psl, 0, x);
    }

    void SeqListPushBack(SeqList* psl, T x)
    {
        SeqListInsert(psl, psl->_size, x);
    }

    void SeqListErase(SeqList* psl, int pos)
    {
        assert(psl);
        assert(psl->_size > 0);
        assert(pos >= 0 && pos < psl->_size);

        for(int i = pos; i < psl->_size-1; i++)
        {
            psl->_a[i] = psl->_a[i + 1];
        }
        psl->_size--;
    }
    
    void SeqListPopFront(SeqList* psl)
    {
        SeqListErase(psl, 0);
    }

    void SeqListPopBack(SeqList* psl)
    {
        SeqListErase(psl, psl->_size-1);
    }

    int SeqListFind(SeqList* psl, T x)
    {
        assert(psl);
        for(int i = 0; i < psl->_size; i++)
        {
            if(psl->_a[i] == x)
                return i;
        }
        return -1;
    }

    void SeqListModify(SeqList* psl, int pos, T x)
    {
        assert(psl);
        assert(pos >= 0 && pos < psl->_size);
        psl->_a[pos] = x;
    }
private:
    T* _a;
    int _size;
    int _capacity;
};